package com.xxwy.lintcodes;

import com.xxwy.BinarySearch;

import javax.management.MXBean;

/**
 * @author xxwy
 * Search a 2D Matrix II
写出一个高效的算法来搜索m×n矩阵中的值，返回这个值出现的次数。

这个矩阵具有以下特性：

- 每行中的整数从左到右是排序的。
- 每一列的整数从上到下是排序的。
- 在每一行或每一列中没有重复的整数。
[
最小
[1, 3, 5, 7],

[2, 4, 7, 8],

[3, 5, 9, 10]
            最大
]
 */
@BinarySearch
public class Num38 {

    public int searchMatrix(int[][] matrix, int target) {
        if(matrix == null|| matrix.length==0){
            return 0;
        }
        if(matrix[0] == null|| matrix[0].length ==0){
            return 0;
        }

        // write your code here
        //行
        int l = matrix.length;
        //列
        int r = matrix[0].length;
        //右上角
        int count = 0;
        int x = 0;
        int y = r-1;
        while (y>=0 && x <l){
            int init = matrix[x][y];
            if(target < init){
                y--;
            }else if (target > init){
                x++;
            }else {
                count++;
                y--;
                x++;
            }
        }
        return count;
    }

}
